#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>
int comp_count = 0;
int swap_count = 0;



static void swap(int *a, int *b)
{
    swap_count++;

    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(unsigned data[], int len)
{
    if(len <= 1)
        return 0;

    int i = 0;
    int j = len-1;
    while(i < j)
    {
        // 从右向左比较，顺序j--，逆序交换
        comp_count++;
        while(data[i]<=data[j] && i<j)
            j--;
        swap(&data[i], &data[j]);

        // 从左向右比较，顺序i++，逆序交换
        comp_count++;
        while(data[i]<=data[j] && i<j)
            i++;
        swap(&data[i], &data[j]);
    }

    return i;
}

void quickSort(unsigned data[], int len)
{
    if(len <= 1)
        return;

    int pivot = partition(data, len); // 一次划分

    quickSort(data, pivot);
    quickSort(data+pivot+1, len-pivot-1);
}
